import java.util.LinkedList;
import java.util.List;

class AnimalShelf0306 {
        private List<Integer> catList  ;
        private List<Integer> dogList ;

    public AnimalShelf0306() {
           catList = new LinkedList<Integer>() ;
           dogList = new LinkedList<Integer>() ;
    }
    
    public void enqueue(int[] animal) {
        if(animal[1] == 0){
          catList.add(animal[0]) ; 
        }else{
           dogList.add(animal[0]);
        }
    }
    
    public int[] dequeueAny() {
         int num = 0 ; 
         int type = 0 ; 
        if(catList.size() == 0 && dogList.size() != 0){
           num =  dogList.remove(0) ;
           type = 1 ;
        }else if(dogList.size() == 0 && catList.size() != 0){
           num = catList.remove(0) ; 
           type = 0 ;
        }else if(dogList.size() != 0 && catList.size() != 0){
           int a = dogList.get(0) ; 
           int b = catList.get(0) ; 
           if(a < b){
             num = dogList.remove(0) ; 
             type = 1 ; 
           }else{
              num = catList.remove(0) ; 
              type = 0 ; 
           }
        }else{
            num  = -1 ;
            type = -1 ;
        }
        return new int[]{num , type} ; 
    }
    
    public int[] dequeueDog() {
         if(dogList.size() == 0){
           return new int[]{-1 , -1} ; 
         }
         int num = dogList.remove(0) ; 
         return new int[]{num , 1} ; 
    }
    
    public int[] dequeueCat() {
           if(catList.size() == 0){
           return new int[]{-1 , -1} ; 
         }
         int num = catList.remove(0) ; 
         return new int[]{num , 0} ; 
    }
}

/**
 * Your AnimalShelf object will be instantiated and called as such:
 * AnimalShelf obj = new AnimalShelf();
 * obj.enqueue(animal);
 * int[] param_2 = obj.dequeueAny();
 * int[] param_3 = obj.dequeueDog();
 * int[] param_4 = obj.dequeueCat();
 */